/*
 * @lc app=leetcode.cn id=21 lang=cpp
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
// struct ListNode {
//      int val;
//      ListNode *next;
//      ListNode() : val(0), next(nullptr) {}
//      ListNode(int x) : val(x), next(nullptr) {}
//      ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    // ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    //     ListNode node; ListNode *cur = &node;
    //     while (list1 != nullptr && list2 != nullptr) {
    //         int lv = list1->val, rv = list2->val;
    //         if (lv >= rv) {
    //             cur->next = list2;
    //             list2 = list2->next;
    //         } else {
    //             cur->next = list1;
    //             list1 = list1->next;
    //         }
    //         cur = cur->next;
    //     }
    //     cur->next = (list1 == nullptr ? list2 : list1);
    //     return node.next; 
    // }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};
// @lc code=end

